"""
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
如果没有任何一种硬币组合能组成总金额，返回 -1。
"""
class Solution:


    def coinChange_opt_opt(self, coins, amount):
        """
        beat 98%
        条件深搜
        :param coins:
        :param amount:
        :return:
        """
        coins.sort(reverse = True)
        self.res = float("inf")
        def dfs(pt,rem,count):
            if rem == 0:
                self.res = min(self.res,count)
            else:
                for i in range(pt,len(coins)):
                    if coins[i] <= rem < coins[i]*(self.res-count):
                        dfs(i,rem-coins[i],count+1)
        for i in range(len(coins)):
            dfs(i,amount,0)
        return self.res


    def coinChange_opt(self, coins, amount):
        """
        依然超时
        :param coins:
        :param amount:
        :return:
        """
        coins.sort(reverse=True)
        self.ans = float("inf")
        def dfs(cur, count):
            if cur == amount:
                self.ans = min(self.ans, count)
            else:
                for x in coins:
                    if cur + x <= amount:
                        dfs(cur+x, count+1)
        dfs(0,0)
        print(self.ans)
        return self.ans if self.ans < 2**31-1 else -1


    def coinChange(self, coins, amount):
        """
        超时
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        dp = [-1]*(amount+1)
        dp[0] = 0
        for i in range(1, len(dp)):
            if i in coins:
                dp[i] = 1
                continue
            minc = float('inf')
            for x in coins:
                if (i - x) in range(1,i) and dp[i-x] != -1:
                    minc = min(minc,dp[i-x]+1)
            if minc != float('inf'): dp[i] = minc
        print(dp[-1])
        return dp[-1]

if __name__ == '__main__':
    s = Solution()
    s.coinChange_opt([1,2,5],11)